<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<HTML>
<HEAD>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<STYLE TYPE="text/css">
		BODY {
			background-color: f5f5f5;
			font-family: arial, verdana; font-size: small;
		}
		H2, H3, A, .tfc {
			color: #000080;
			font-family: arial, verdana; font-size: small;
		}
		PRE { 
		    font-family: monospace;
			border: 1px lightgrey dotted;
		    white-space: pre; 
		    color: black;
		    background-color: #efefef; 
		}
		TABLE {
			float: right;
			border-collapse: collapse;
			border-top: 1px solid #000000;
			border-right: 1px solid #000000;
			border-left: 1px solid #000000;
		}
		TH {
			padding-top: 2px;
			padding-bottom: 2px;
			padding-right: 5px;
			padding-left: 5px;
		}
		TD {
			padding-top: 2px;
			padding-bottom: 2px;
			padding-right: 5px;
			padding-left: 5px;
			border-bottom: 1px solid #000000;
			border-right: 1px solid #000000;
			font-family: arial, verdana; font-size: small;
		}
	</STYLE>
<TITLE>Hashmap</TITLE>
</HEAD>
<BODY>
<H1>7. Hashmap</H1>
A  <I>hashmap</I>(3m)  object  associates  keys  with data pointers. Large numbers of elements may be stored and retrieved efficiently.
<p>
</p>
Memory management of keys and data pointers is the resposibility of the user although <TT>del_fn</TT> function pointers (defined in <TT>allocator</TT>(3m)) may be specified with some <TT>hashmap</TT> functions to assist the user with this task.
<H3>7.1. Definitions</H3>
<A name="Hashmap Definitions"></A>
<P>
<B CLASS="tfc">Hashmap Definitions</B>
<BR>
<PRE>

  typedef unsigned long (*hash_fn)(const void *object, void *context);
  typedef int (*cmp_fn)(const void *object1, const void *object2, void *context);
  
  unsigned long hash_text(const void *text, void *context);
  unsigned long cmp_text(const void *text1, const void *text2, void *context);
  </PRE>
The <TT>hash_text</TT> function is a suitable <TT>hash_fn</TT> for character strings. This function is actually a macro for either <TT>hash_str</TT> or <TT>hash_wcs</TT> that accept multi-byte or wide character strings depending on wheather or not <tt>USE_WCHAR</tt> is defined.
<p>
</p>
The <TT>cmp_text</TT> function is a suitable <TT>cmp_fn</TT> for character strings. This function is actually a macro for either <TT>cmp_str</TT> or <TT>cmp_wcs</TT> that accept multi-byte or wide character strings depending on wheather or not <tt>USE_WCHAR</tt> is defined.
<BR>
</P>
<H3>7.2. Memory management functions</H3>These functions should be used to create and destroy <I>hashmap</I> objects.<A name="init"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_init</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_init(struct hashmap *h,
           unsigned int load_factor,
           hash_fn hash,
           cmp_fn cmp,
           void *context,
           struct allocator *al);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_init</TT> function initializes the memory at <tt>h</tt> as a <TT>hashmap</TT> with no elements. The <tt>load_factor</tt> parameter must be an integer between 1 and 100 indicating when the map should be resized. If a value of 0 is specified, the default value of 75 will be used meaning the map will be increased when 75 of every 100 spaces for elements are occupied.
<p>
</p>
If the <tt>hash</tt> parameter is not <TT>NULL</TT> it will be used to generate a hash value given a key and the specified <tt>context</tt> object. Given a set of keys the <tt>hash</tt> function should generate an even distribution of values. If the <tt>hash</tt> parameter is <TT>NULL</TT> a key's memory address will be used as it's hash value.
<p>
</p>
If the <tt>cmp</tt> parameter is not <TT>NULL</TT> it will used to compare two keys for equality. This function should return 0 if two keys are equal and non-zero if they are not. If the <tt>cmp</tt> parameter is <TT>NULL</TT> the memory addresses of the two keys will be compared.
<p>
</p>
The <tt>al</tt> parameter is an <TT>allocator</TT>(3m) from which all memory associated with this <TT>hashmap</TT> should be allocated. As with the <TT>allocator</TT> functions, a <TT>NULL</TT> allocator indicates the <TT>stdlib_allocator</TT> should be used.
<p>
</p>
The following example illustrates how to initialize a <TT>hashmap</TT> and use it to store the object <tt>data</tt> associated with the character string "name".
<PRE>

  struct hashmap hm;
  struct foo data, *out;
  hashmap_init(&amp;hm,
  	0,                             /* default load factor of 75 */
  	hash_text,                    /* default text hash function */
  	cmp_text,                  /* default text compare function */
  	NULL, /* hash_fn and cmp_fn function do not require context */
  	NULL);                          /* use the stdlib_allocator */
  hashmap_put(&amp;hm, "name", &amp;data);
  out = hashmap_get(&amp;hm, "name");
  /* out now points to data */
  </PRE>
	<B>Returns</B>
<BR>
The <TT>hashmap_init</TT> function returns 0 on success or -1 for failure in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<A name="deinit"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_deinit</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_deinit(struct hashmap *h,
           del_fn key_del,
           del_fn data_del,
           void *context);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_deinit</TT> function deinitializes the <TT>hashmap</TT> <tt>h</tt>. If the <tt>key_del</tt> or <tt>data_del</tt> functions are not <TT>NULL</TT> they will be called with the <tt>context</tt> object and each key and/or data object in the map. Any memory associated with the <TT>hashmap</TT> will be released.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_deinit</TT> function returns 0 on success or -1 for failure in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<A name="new"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_new</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  struct hashmap *hashmap_new(hash_fn hash, cmp_fn cmp, void *context, struct allocator *al);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_new</TT> function allocates memory for a new <TT>hashmap</TT> object and initializes it with <TT>hashmap_init</TT>
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_new</TT> function returns a new <tt>struct hashmap *</tt> object that contains no elements or <TT>NULL</TT> if the operation failed in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<A name="del"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_del</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_del(struct hashmap *h, del_fn key_del, del_fn data_del, void *context);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_del</TT> function deinitializes the <TT>hashmap</TT> <tt>h</tt> with the <TT>hashmap_deinit</TT> function and then releases the <tt>h</tt> object itself.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_del</TT> function returns 0 on success or -1 for failure in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<A name="clear"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_clear</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_clear(struct hashmap *h, del_fn key_del, del_fn data_del, void *context);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_clear</TT> function clears all elements from the <TT>hashmap</TT> <tt>h</tt>.
If the <tt>key_del</tt> or <tt>data_del</tt> functions are not <TT>NULL</TT> they will be called with the <tt>context</tt> object and each key and/or data object in the map.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_clear</TT> function returns 0 on success or -1 for failure in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<A name="clean"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_clean</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_clean(struct hashmap *h);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_clean</TT> function will release excess memory allocated by the <TT>hashmap</TT> <tt>h</tt>. See the <TT>allocator_set_reclaim</TT> function.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_clean</TT> function returns the number of unused elements released (possibly 0) or -1 if an error occured in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<H3>7.3. Map functions</H3>
<A name="put"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_put</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_put(struct hashmap *h, void *key, void *data);<BR>
</PRE>
<B>Description</B>
<BR>
Put a data pointer into the map with the key <tt>key</tt>. If an element with the same key already exists in the map, -1 will be returned and <tt>errno</tt> will be set to <tt>EEXIST</tt>. If another error occurs, -1 will be returned and <tt>errno</tt> will be set to an appropriate value.
	<BR>
<P>
</P>
<A name="get"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_get</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  void *hashmap_get(const struct hashmap *h, const void *key);<BR>
</PRE>
<B>Description</B>
<BR>
Retrieve a data pointer from the map with the key <tt>key</tt>.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_get</TT> function returns the data pointer being retrieved or <TT>NULL</TT> if the element was not found. <TT>NULL</TT> will also be returned if the <tt>h</tt> or <tt>key</tt> parameters are <tt>NULL</tt> but this function does not set <tt>errno</tt> to any value.
	<P>
</P>
<A name="is_empty"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_is_empty</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_is_empty(struct hashmap *h);<BR>
</PRE>
<B>Description</B>
<BR>
Returns 1 if the map is empty and 0 otherwise.
	<BR>
<P>
</P>
<A name="size"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_size</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  unsigned int hashmap_size(struct hashmap *h);<BR>
</PRE>
<B>Description</B>
<BR>
Returns the number of data pointers in the map.
	<BR>
<B>Returns</B>
<BR>
The <TT>hashmap_size</TT> function returns the number of data pointers in the map. If <tt>h</tt> is <tt>NULL</tt>, zero is returned.
	<P>
</P>
<A name="iterate"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_iterate</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  void hashmap_iterate(void *h, iter_t *iter);<BR>
</PRE>
<B>Description</B>
<BR>
Enumerate each key in the map. The <tt>hashmap_iterate</tt> function initializes the <tt>iter</tt> object to point to the  beginning  of the map. With each call to <tt>hashmap_next</tt>, a key will be returned.  When  all  keys  have been enumerated, <tt>hashmap_next</tt> will return <tt>NULL</tt>. Keys are not returned in any particular order.
<p>
</p>
Modifying the map during the enumeration is permitted however should adding or removing data cause the table to be resized, not all keys may be enumerated and some keys may be returned more than once. Therefore, to make multiple modifications during the enumeration it may be desirable to first create a snapshot of the keys in an array or list.
	<BR>
<P>
</P>
<A name="next"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_next</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  void *hashmap_next(void *h, iter_t *iter);<BR>
</PRE>
<B>Returns</B>
<BR>
The <TT>hashmap_next</TT> function returns the next key in the map or <tt>NULL</tt> if all keys have been enumerated.
	<P>
</P>
<A name="remove"></A>
<P>
</P>
<B CLASS="tfc">The <TT>hashmap_remove</TT> function</B>
<BR>
<B>Synopsis</B>
<PRE>
<BR>  #include &lt;mba/hashmap.h&gt;
  int hashmap_remove(struct hashmap *h, void **key, void **data);<BR>
</PRE>
<B>Description</B>
<BR>
The <TT>hashmap_remove</TT> function removes the element associated with <tt>key</tt> from the <TT>hashmap</TT> <tt>h</tt> and stores pointers to the original key and data in the provided <tt>key</tt> and <tt>data</tt> parameters.
<p>
</p>
The following is an example of removing an element from a <TT>hashmap</TT>.
<PRE>

  char *key = name;
  struct foo *data;
  hashmap_remove(hm, (void **)&amp;key, (void **)&amp;data);
  /* free data if necessary */
  </PRE>
	<B>Returns</B>
<BR>
The <TT>hashmap_remove</TT> function returns 0 on success or -1 for failure in which case <tt>errno</tt> will be set to an appropriate value.
	<P>
</P>
<HR NOSHADE>
<small>
Copyright 2004 Michael B. Allen &lt;mba2000 ioplex.com&gt;
</small>
</BODY>
</HTML>
